﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace g4
{
    /// <summary>
    /// 平面孔洞填充器：用于填充网格中的平面孔洞
    /// 核心原理：将孔洞边界映射到2D平面，使用2D算法填充后再映射回3D空间
    /// 支持处理嵌套孔洞（如 torus 切割后的孔洞）等复杂情况
    /// 
    /// 实现流程：
    /// 1. 使用 PlanarComplex 处理输入的2D多边形（排序、区分内外边界）
    /// 2. 使用 MeshInsertUVPolyCurve 将每个2D多边形插入生成的平面网格
    /// 3. 填充网格的分辨率由 FillTargetEdgeLen 控制
    /// 
    /// 优势：理论上比Delaunay三角化更能处理几何退化情况
    /// 限制：依赖 MeshInsertUVPolyCurve 生成与输入多边形一一对应的边界环，失败时可能无法正确缝合
    /// </summary>
    public class PlanarHoleFiller
    {
        /// <summary>
        /// 包含孔洞的目标网格
        /// </summary>
        public DMesh3 Mesh;

        /// <summary>
        /// 孔洞所在平面的原点
        /// </summary>
        public Vector3d PlaneOrigin;

        /// <summary>
        /// 孔洞所在平面的法向量
        /// </summary>
        public Vector3d PlaneNormal;

        /// <summary>
        /// 填充网格的目标边长度（控制细分精度）
        /// 设为 double.MaxValue 时使用零长度细分（最低精度）
        /// </summary>
        public double FillTargetEdgeLen = double.MaxValue;

        /// <summary>
        /// 是否合并填充区域与原始网格的边界
        /// 某些情况下填充成功但合并会产生新孔洞，此时可关闭此选项
        /// </summary>
        public bool MergeFillBoundary = true;


        /* 错误反馈字段 */

        /// <summary>
        /// 标记输出是否存在裂缝（填充区域与原始网格未完全缝合）
        /// </summary>
        public bool OutputHasCracks = false;

        /// <summary>
        /// 插入2D多边形失败的次数
        /// </summary>
        public int FailedInsertions = 0;

        /// <summary>
        /// 合并填充边界失败的次数
        /// </summary>
        public int FailedMerges = 0;


        // 平面局部坐标系（若未手动设置则自动计算）
        /// <summary>
        /// 平面内的X轴方向向量（与法向量垂直）
        /// </summary>
        Vector3d PlaneX;

        /// <summary>
        /// 平面内的Y轴方向向量（与法向量和PlaneX垂直）
        /// </summary>
        Vector3d PlaneY;

        /// <summary>
        /// 填充环结构体：关联边界环与对应的2D多边形
        /// </summary>
        class FillLoop
        {
            public EdgeLoop edgeLoop; // 3D边界环
            public Polygon2d poly;    // 映射到2D的多边形
        }

        /// <summary>
        /// 需要填充的边界环列表（包含对应的2D多边形）
        /// </summary>
        List<FillLoop> Loops = new List<FillLoop>();

        /// <summary>
        /// 2D多边形的边界框（用于缩放和平移以提高计算精度）
        /// </summary>
        AxisAlignedBox2d Bounds;


        /// <summary>
        /// 构造函数：初始化平面孔洞填充器
        /// </summary>
        /// <param name="mesh">包含孔洞的目标网格</param>
        public PlanarHoleFiller(DMesh3 mesh)
        {
            Mesh = mesh;
            Bounds = AxisAlignedBox2d.Empty;
        }

        /// <summary>
        /// 构造函数：从平面切割结果初始化（处理切割产生的孔洞）
        /// </summary>
        /// <param name="cut">平面切割器实例（已执行切割并产生孔洞）</param>
        public PlanarHoleFiller(MeshPlaneCut cut)
        {
            Mesh = cut.Mesh;
            AddFillLoops(cut.CutLoops); // 添加切割产生的边界环
            SetPlane(cut.PlaneOrigin, cut.PlaneNormal); // 设置切割平面参数
        }


        /// <summary>
        /// 设置孔洞所在平面的参数（自动计算平面内的X、Y轴）
        /// </summary>
        /// <param name="origin">平面原点</param>
        /// <param name="normal">平面法向量</param>
        public void SetPlane(Vector3d origin, Vector3d normal)
        {
            PlaneOrigin = origin;
            PlaneNormal = normal;
            // 计算平面内的正交坐标系（X、Y轴与法向量垂直）
            Vector3d.ComputeOrthogonalComplement(1, PlaneNormal, ref PlaneX, ref PlaneY);
        }

        /// <summary>
        /// 手动设置孔洞所在平面的完整参数（包含平面内的X、Y轴）
        /// </summary>
        /// <param name="origin">平面原点</param>
        /// <param name="normal">平面法向量</param>
        /// <param name="planeX">平面内X轴方向</param>
        /// <param name="planeY">平面内Y轴方向</param>
        public void SetPlane(Vector3d origin, Vector3d normal, Vector3d planeX, Vector3d planeY)
        {
            PlaneOrigin = origin;
            PlaneNormal = normal;
            PlaneX = planeX;
            PlaneY = planeY;
        }


        /// <summary>
        /// 添加单个需要填充的边界环
        /// </summary>
        /// <param name="loop">3D边界环</param>
        public void AddFillLoop(EdgeLoop loop)
        {
            Loops.Add(new FillLoop() { edgeLoop = loop });
        }

        /// <summary>
        /// 添加多个需要填充的边界环
        /// </summary>
        /// <param name="loops">3D边界环集合</param>
        public void AddFillLoops(IEnumerable<EdgeLoop> loops)
        {
            foreach (var loop in loops)
                AddFillLoop(loop);
        }


        /// <summary>
        /// 执行孔洞填充操作：生成填充网格并合并到原始网格
        /// 失败时返回false，错误信息可通过错误反馈字段查看
        /// </summary>
        /// <returns>填充是否完全成功</returns>
        public bool Fill()
        {
            // 1. 将3D边界环映射为2D多边形
            compute_polygons();

            // 2. 将2D多边形平移缩放至单位盒（提高计算精度）
            Vector2d shiftOrigin = Bounds.Center; // 平移原点（边界框中心）
            double scale = 1.0 / Bounds.MaxDim;   // 缩放因子（归一化到单位盒）
            foreach (var floop in Loops)
            {
                floop.poly.Translate(-shiftOrigin); // 平移到原点
                floop.poly.Scale(scale * Vector2d.One, Vector2d.Zero); // 缩放到单位盒
            }

            // 3. 建立平面复杂结构（管理多边形关系，区分内外边界）
            Dictionary<PlanarComplex.Element, int> elemToLoopMap = new Dictionary<PlanarComplex.Element, int>();
            PlanarComplex complex = new PlanarComplex();
            for (int i = 0; i < Loops.Count; ++i)
            {
                var elem = complex.Add(Loops[i].poly); // 添加多边形到复杂结构
                elemToLoopMap[elem] = i; // 记录元素与边界环的映射
            }

            // 4. 提取2D固体区域（区分外边界和内边界/孔洞）
            PlanarComplex.SolidRegionInfo solids = complex.FindSolidRegions(
                PlanarComplex.FindSolidsOptions.SortPolygons);

            // 5. 填充每个2D固体区域
            List<Index2i> failedInserts = new List<Index2i>();
            List<Index2i> failedMerges = new List<Index2i>();
            for (int fi = 0; fi < solids.Polygons.Count; ++fi)
            {
                var gpoly = solids.Polygons[fi]; // 带孔洞的多边形
                PlanarComplex.GeneralSolid gsolid = solids.PolygonsSources[fi]; // 多边形来源信息

                // 6. 生成基础平面网格（用于插入2D多边形）
                MeshGenerator meshgen;
                float planeW = 1.5f; // 平面网格宽度（稍大于单位盒，确保覆盖）
                int nDivisions = 0;

                // 根据目标边长度计算细分数量
                if (FillTargetEdgeLen < double.MaxValue && FillTargetEdgeLen > 0)
                {
                    int n = (int)((planeW / (float)scale) / FillTargetEdgeLen) + 1;
                    nDivisions = (n <= 1) ? 0 : n; // 确保至少1个细分
                }

                // 生成基础网格（简单矩形或细分网格）
                if (nDivisions == 0)
                {
                    meshgen = new TrivialRectGenerator()
                    {
                        IndicesMap = new Index2i(1, 2),
                        Width = planeW,
                        Height = planeW
                    };
                }
                else
                {
                    meshgen = new GriddedRectGenerator()
                    {
                        IndicesMap = new Index2i(1, 2),
                        Width = planeW,
                        Height = planeW,
                        EdgeVertices = nDivisions // 每条边的顶点数（控制细分密度）
                    };
                }
                DMesh3 fillMesh = meshgen.Generate().MakeDMesh();
                fillMesh.ReverseOrientation(); // 反转朝向（确保与原始网格一致）

                // 7. 收集需要插入的多边形（外边界+所有内边界/孔洞）
                List<Polygon2d> polys = new List<Polygon2d>() { gpoly.Outer };
                polys.AddRange(gpoly.Holes);

                // 存储每个多边形插入后对应的顶点
                int[][] polyVertices = new int[polys.Count][];

                // 8. 将每个2D多边形插入基础平面网格
                for (int pi = 0; pi < polys.Count; ++pi)
                {
                    MeshInsertUVPolyCurve insert = new MeshInsertUVPolyCurve(fillMesh, polys[pi]);
                    // 验证多边形有效性
                    ValidationStatus status = insert.Validate(MathUtil.ZeroTolerancef * scale);
                    bool failed = true;
                    if (status == ValidationStatus.Ok)
                    {
                        if (insert.Apply())
                        { // 执行插入
                            insert.Simplify(); // 简化插入结果（移除冗余顶点）
                            polyVertices[pi] = insert.CurveVertices;
                            // 检查插入结果是否与输入多边形匹配（顶点数一致）
                            failed = (insert.Loops.Count != 1) ||
                                     (insert.Loops[0].VertexCount != polys[pi].VertexCount);
                        }
                    }
                    if (failed)
                        failedInserts.Add(new Index2i(fi, pi));
                }

                // 9. 移除平面网格中多边形外部的三角形
                List<int> removeT = new List<int>();
                foreach (int tid in fillMesh.TriangleIndices())
                {
                    Vector3d centroid = fillMesh.GetTriCentroid(tid); // 三角形重心
                    if (!gpoly.Contains(centroid.xy)) // 重心不在多边形内则移除
                        removeT.Add(tid);
                }
                foreach (int tid in removeT)
                    fillMesh.RemoveTriangle(tid, true, false);

                // 10. 将填充网格从2D单位盒映射回3D空间
                MeshTransforms.PerVertexTransform(fillMesh, (v) => {
                    Vector2d v2 = v.xy;
                    v2 /= scale; // 逆缩放
                    v2 += shiftOrigin; // 逆平移
                    return to3D(v2); // 转换为3D坐标
                });

                // 11. 建立填充网格与原始网格的顶点映射（用于合并边界）
                IndexMap mergeMapV = new IndexMap(true);
                if (MergeFillBoundary)
                {
                    for (int pi = 0; pi < polys.Count; ++pi)
                    {
                        if (polyVertices[pi] == null)
                            continue;
                        int[] fillLoopVerts = polyVertices[pi]; // 填充网格的边界顶点
                        int nv = fillLoopVerts.Length;

                        // 找到对应的原始边界环
                        PlanarComplex.Element sourceElem = (pi == 0) ? gsolid.Outer : gsolid.Holes[pi - 1];
                        int loopi = elemToLoopMap[sourceElem];
                        EdgeLoop sourceLoop = Loops[loopi].edgeLoop;

                        // 构建顶点合并映射
                        List<int> badIndices = build_merge_map(
                            fillMesh, fillLoopVerts, Mesh, sourceLoop.Vertices,
                            MathUtil.ZeroTolerancef, mergeMapV);

                        // 检查合并是否存在错误
                        if (badIndices != null && badIndices.Count > 0)
                        {
                            failedInserts.Add(new Index2i(fi, pi));
                            OutputHasCracks = true;
                        }
                    }
                }

                // 12. 将填充网格合并到原始网格
                MeshEditor editor = new MeshEditor(Mesh);
                int[] mapV; // 顶点映射表（填充网格顶点 -> 原始网格顶点）
                editor.AppendMesh(fillMesh, mergeMapV, out mapV, Mesh.AllocateTriangleGroup());
            }

            // 13. 更新错误统计
            FailedInsertions = failedInserts.Count;
            FailedMerges = failedMerges.Count;
            return (FailedInsertions == 0 && FailedMerges == 0);
        }


        /// <summary>
        /// 构建填充网格边界顶点与原始网格边界顶点的映射关系
        /// 理想情况下为1-1对应，否则通过暴力搜索寻找最佳匹配
        /// 仅保留唯一对应关系（避免一个顶点匹配多个原始顶点）
        /// </summary>
        /// <param name="fillMesh">填充网格</param>
        /// <param name="fillLoopV">填充网格的边界顶点</param>
        /// <param name="targetMesh">原始网格</param>
        /// <param name="targetLoopV">原始网格的边界顶点</param>
        /// <param name="tol">匹配容差（距离阈值）</param>
        /// <param name="mergeMapV">输出：顶点合并映射（填充顶点ID -> 原始顶点ID）</param>
        /// <returns>未成功合并的填充顶点索引列表</returns>
        List<int> build_merge_map(DMesh3 fillMesh, int[] fillLoopV,
                             DMesh3 targetMesh, int[] targetLoopV,
                             double tol, IndexMap mergeMapV)
        {
            // 先尝试简单1-1匹配（顶点数相同且顺序对应）
            if (fillLoopV.Length == targetLoopV.Length)
            {
                if (build_merge_map_simple(fillMesh, fillLoopV, targetMesh, targetLoopV, tol, mergeMapV))
                    return null;
            }

            // 复杂匹配：处理顶点数不同或顺序不对应的情况
            int nFill = fillLoopV.Length, nTarget = targetLoopV.Length;
            bool[] doneFill = new bool[nFill], doneTarget = new bool[nTarget];
            int[] countFill = new int[nFill], countTarget = new int[nTarget];
            List<int> errorV = new List<int>(); // 未匹配的填充顶点索引

            // 存储填充顶点与原始顶点的匹配关系
            SmallListSet matchFill = new SmallListSet();
            matchFill.Resize(nFill);

            double tolSqr = tol * tol; // 容差平方（避免开方运算）
            for (int i = 0; i < nFill; ++i)
            {
                if (!fillMesh.IsVertex(fillLoopV[i]))
                {
                    doneFill[i] = true;
                    errorV.Add(i);
                    continue;
                }
                matchFill.AllocateAt(i);
                Vector3d v = fillMesh.GetVertex(fillLoopV[i]);
                // 寻找所有距离在容差内的原始顶点
                for (int j = 0; j < nTarget; ++j)
                {
                    Vector3d v2 = targetMesh.GetVertex(targetLoopV[j]);
                    if (v.DistanceSquared(ref v2) < tolSqr)
                    {
                        matchFill.Insert(i, j);
                    }
                }
            }

            // 仅保留唯一匹配的顶点
            for (int i = 0; i < nFill; ++i)
            {
                if (doneFill[i]) continue;
                if (matchFill.Count(i) == 1)
                { // 唯一匹配
                    int j = matchFill.First(i);
                    mergeMapV[fillLoopV[i]] = targetLoopV[j];
                    doneFill[i] = true;
                }
            }

            // 收集未匹配的顶点
            for (int i = 0; i < nFill; ++i)
            {
                if (!doneFill[i])
                    errorV.Add(i);
            }

            return errorV;
        }


        /// <summary>
        /// 简单顶点映射：验证填充网格与原始网格的边界顶点是否1-1对应（顺序和位置均匹配）
        /// 匹配成功则添加到合并映射并返回true
        /// </summary>
        bool build_merge_map_simple(DMesh3 fillMesh, int[] fillLoopV,
                                    DMesh3 targetMesh, int[] targetLoopV,
                                    double tol, IndexMap mergeMapV)
        {
            if (fillLoopV.Length != targetLoopV.Length)
                return false; // 顶点数不同，无法1-1匹配

            int nv = fillLoopV.Length;
            // 验证每个顶点的位置是否在容差内
            for (int k = 0; k < nv; ++k)
            {
                if (!fillMesh.IsVertex(fillLoopV[k]))
                    return false;
                Vector3d fillV = fillMesh.GetVertex(fillLoopV[k]);
                Vector3d sourceV = Mesh.GetVertex(targetLoopV[k]);
                if (fillV.Distance(sourceV) > tol)
                    return false;
            }

            // 建立1-1映射
            for (int k = 0; k < nv; ++k)
                mergeMapV[fillLoopV[k]] = targetLoopV[k];
            return true;
        }


        /// <summary>
        /// 将3D边界环映射为2D多边形（计算每个顶点的2D坐标并构建多边形）
        /// </summary>
        void compute_polygons()
        {
            Bounds = AxisAlignedBox2d.Empty; // 重置边界框
            for (int i = 0; i < Loops.Count; ++i)
            {
                EdgeLoop loop = Loops[i].edgeLoop;
                Polygon2d poly = new Polygon2d();

                // 逐个顶点映射到2D
                foreach (int vid in loop.Vertices)
                {
                    Vector2d v = to2D(Mesh.GetVertex(vid));
                    poly.AppendVertex(v);
                }

                Loops[i].poly = poly;
                Bounds.Contain(poly.Bounds); // 更新边界框
            }
        }


        /// <summary>
        /// 检查2D点是否在多个多边形内
        /// </summary>
        /// <param name="v2">2D点</param>
        /// <param name="polys">多边形集合</param>
        /// <param name="all">是否需要在所有多边形内</param>
        /// <returns>是否满足包含条件</returns>
        bool inPolygon(Vector2d v2, List<GeneralPolygon2d> polys, bool all = false)
        {
            int insideCount = 0;
            foreach (var poly in polys)
            {
                if (poly.Contains(v2))
                {
                    if (!all) return true; // 只要在一个多边形内
                    insideCount++;
                }
            }
            return all && insideCount == polys.Count; // 需在所有多边形内
        }

        /// <summary>
        /// 将3D点映射到平面的2D坐标
        /// </summary>
        /// <param name="v">3D点</param>
        /// <returns>2D坐标（在PlaneX和PlaneY方向上的投影）</returns>
        Vector2d to2D(Vector3d v)
        {
            Vector3d dv = v - PlaneOrigin;
            // 移除法向量方向的分量（投影到平面内）
            dv -= dv.Dot(PlaneNormal) * PlaneNormal;
            // 投影到平面的X、Y轴
            return new Vector2d(PlaneX.Dot(dv), PlaneY.Dot(dv));
        }

        /// <summary>
        /// 将2D点映射回3D空间
        /// </summary>
        /// <param name="v">2D坐标</param>
        /// <returns>3D点（在平面上的位置）</returns>
        Vector3d to3D(Vector2d v)
        {
            return PlaneOrigin + PlaneX * v.x + PlaneY * v.y;
        }
    }
}